public class ChkPalindrome {
    public static boolean chkPalindrome(MySingleList.ListNode head) {
        //寻找链表中间结点
        MySingleList.ListNode fast = head;
        MySingleList.ListNode slow = head;

        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        //slow所指向的结点即为链表的中间结点
        MySingleList.ListNode newHead = reverseList(slow);
        MySingleList.ListNode tail = newHead;

        //判断是否为回文
        MySingleList.ListNode cur = head;
        while(cur != tail) {
            if(cur.val != tail.val) {
                return false;
            }
            if(cur.next == tail) {
                return true;
            }
            cur = cur.next;
            tail = tail.next;
        }

        return true;
    }

    public static MySingleList.ListNode reverseList(MySingleList.ListNode head) {
        //递归出口
        if(head == null || head.next == null) {
            return head;
        }

        //递归逆置下一个结点为头部结点的单链表
        MySingleList.ListNode newHead = reverseList(head.next);

        //将头部结点拼接到逆置完成的单链表之后
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
         MySingleList list = new MySingleList();
         list.addLast(1);
         list.addLast(2);
         list.addLast(3);
         list.addLast(4);

        System.out.println(chkPalindrome(list.head));
    }
}
